#include<iostream>
#include <vector>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f // 定义∞
#define MAXN 21 // 最大的n

// 人员、任务数
int n = 4;

// 成本表
int c[MAXN][MAXN] = {{9,2,7,8}, {6,4,3,7}, {5,8,1,8}, {7,6,9,4}};

// 最优解向量
vector<int> bestx;

// 最优解的成本
int bestc = INF;

// used[j]表示任务j是否已经分配人员
bool used[MAXN];	

// 累计解个数
int sum = 0;

// 为第i个人员分配任务
void dfs(vector<int> &x, int cost, int i)
{
	sum++;
	
	// 到达叶子结点
	if (i >= n)
	{
		// 比较求最优解
		if (cost < bestc)
		{
			bestc=cost;
			bestx=x;
		}
	}
	else
	{
		// 为人员i试探任务j:1到n
		for (int j=0; j<n; j++)
		{
			// 若任务j还没有分配
			if (!used[j])
			{
				// 任务j分配给人员i
				used[j]=true;
				x[i]=j;
				cost += c[i][j];
				
				// 为人员i+1分配任务
				dfs(x, cost, i+1);
				
				// 回退
				used[j]=false;
				x[i]=0;
				cost-=c[i][j];
			}
		}
	}
}

// 分配任务
void alloction()
{
	// used初始化为false
	memset(used, false, sizeof(used));
	
	// 临时解
	vector<int> x(n, 0);	
	
	// 临时解的成本
	int cost = 0;
	
	// 从人员0开始
	dfs(x, cost, 0);	
	
	// 打印最优成本
	printf("sum=%d\n",sum);
}

int main()
{
	// used初始化为false
	memset(used, 0, sizeof(used));
	
	// 分配任务
	alloction();	
	
	// 输出最优方案
	printf("最优方案:\n");
	for (int k=0; k<n; k++)
		printf("   第%d个人安排任务%d\n", k, bestx[k]);
	printf("   总成本=%d\n", bestc);
	return 0;
}






